package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

/**
 * LC654.最大二叉树
 */
public class LC654 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length);
    }

    private TreeNode buildTree(int[] nums, int start, int end) {
        if (start >= end) return null;
        int rootVal = nums[start];
        int rootIndex = start;
        for (int i = start + 1; i < end; i++) {
            if (nums[i] > rootVal) {
                rootVal = nums[i];
                rootIndex = i;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(nums, start, rootIndex);
        root.right = buildTree(nums, rootIndex + 1, end);
        return root;
    }

    public static void main(String[] args) {
        LC654 alg = new LC654();
        TreeNode treeNode = alg.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
        System.out.println(treeNode);
    }
}
